The present invention relates generally to radio telecommunication networks. More particularly, and not by way of limitation, the present invention is directed to an efficient method of inverting nearly Toeplitz or block Toeplitz matrices in adaptive wireless receivers.
The ability to adapt to different propagation and interference conditions is highly important in modern wireless receivers. In a typical adaptive receiver, various parameters that characterize the current communication link conditions, such as channel response and interference statistics, are often estimated over a limited number of received signal samples. The core of such estimation processes often requires the inversion of matrices that have approximately Toeplitz or block Toeplitz forms. A Toeplitz matrix is any n×n matrix with values constant along each top-left-to-lower-right diagonal. More precisely, if T is a Toeplitz matrix, then the element in the i-th row and the j-th column, for any i and j, can be expressed as [Tij]=a(i-j) for some scalar function, a(k), where k is an integer, as shown below:
  T  =      [                                        a            ⁡                          (              0              )                                                            a            ⁡                          (                              -                1                            )                                                …                                      a            ⁡                          (                              -                                  (                                      n                    -                    2                                    )                                            )                                                            a            ⁡                          (                              -                                  (                                      n                    -                    1                                    )                                            )                                                                        a            ⁡                          (              1              )                                                            a            ⁡                          (              0              )                                                            a            ⁡                          (                              -                1                            )                                                ⋮                                      a            ⁡                          (                              -                                  (                                      n                    -                    2                                    )                                            )                                                            ⋮                                      a            ⁡                          (              1              )                                                            a            ⁡                          (              0              )                                                            a            ⁡                          (                              -                1                            )                                                ⋮                                                  a            ⁡                          (                              n                -                2                            )                                                ⋮                                      a            ⁡                          (              1              )                                                            a            ⁡                          (              0              )                                                            a            ⁡                          (                              -                1                            )                                                                        a            ⁡                          (                              n                -                1                            )                                                            a            ⁡                          (                              n                -                2                            )                                                …                                      a            ⁡                          (              1              )                                                            a            ⁡                          (              0              )                                            ]  A block Toeplitz matrix is defined in the same manner except that a(k) is a p×p matrix function where n is divisible by the integer p.
An exemplary use of nearly Toeplitz or block Toeplitz matrices is found in equalizers that address the problem of multipath fading of wireless channels. Multipath fading is a key phenomenon that makes reliable transmission difficult in a wireless communication system, and is typically caused by reflections of the transmitted radio signal from numerous local scattering objects situated around the receiver. Not only is such multi-path fading time-varying, but it also causes intersymbol interference (ISI) at the receiver. To mitigate the detrimental effect of ISI, a wireless receiver typically uses an equalizer. One of the best and most popular equalization method is the maximum-likelihood sequence estimation (MLSE). To operate properly, an MLSE equalizer requires an accurate estimate of the wireless channel. Because of the time-varying nature of the fading channel, the channel estimate often needs to be updated periodically. The least-squares (LS) method is one of the most commonly used methods of channel estimation. To compute an LS channel estimate, it is known that the inversion of so-called Fisher information, which is a matrix that is nearly, but not exactly Toeplitz, is required. (See, Crozier, S. N. et. al., “Least sum of squared errors (LSSE) channel estimation,” IEEE Proceedings-F 1991, pp. 371-378, which is hereby incorporated by reference.)
Although an MLSE equalizer can provide excellent performance in terms of reducing the overall bit error rates, its complexity of implementation grows exponentially with the length of the channel estimate. Consequently, in situations where the channel response is relatively long, a reduced complexity equalizer, such as the decision-feedback equalizer (DFE) is often used instead. A DFE equalizer demodulates the transmitted symbols sequentially one after another and uses the demodulated symbols of previous time instants to estimate the effect of ISI that these previous symbols cause at the next time instant. In order to improve the estimate of ISI, a prefilter is often used before a DFE equalizer to transform the effective channel response so that most of the energy of the resulting channel response, after prefiltering, is concentrated in the front-most channel tap. Since the original channel response may vary with time, the prefilter also needs to be computed periodically. One of the most commonly used prefilters is the minimum-mean-squared-error (MMSE) prefilter. To compute an MMSE prefilter, the receiver needs to invert a nearly Toeplitz matrix that depends on the channel response as well as the variance of noise in the received signal. (See, Proakis, John G., Digital Communications, 2nd edition, McGraw-Hill, 1989, which is hereby incorporated by reference.)
For yet another example, consider a high-capacity cellular communication network where radio frequencies are being reused in different geographical areas within close proximity. In such a network, mutual interference among users occupying the same radio channel is often a major source of signal disturbance. Thus, mobile receivers that are capable of suppressing interference are highly desirable. A simple and effective method of suppressing interference is to model the interference as colored noise and to attempt to whiten the noise using a linear predictive filter, commonly referred to as a whitening filter. The whitening filter flattens the frequency spectrum of the noise (or “whitens” the noise) by subtracting from it the portion that is predictable using estimates of noise samples from previous time instants. Through this whitening process, the noise power is reduced. Since the spectrum of the interference typically varies with time, the receiver often needs to adaptively compute such a whitening filter based on the received signal. A popular and effective method of computing this whitening filter, or equivalently of estimating the interference spectrum, is the covariance method. (See, Kay, S. M., Modern Spectral Estimation, Theroy & Application, Prentice-Hall, 1988, which is hereby incorporated by reference.) The covariance method requires the calculation of the inverse of a noise covariance matrix that is nearly, but not exactly Toeplitz. This covariance matrix becomes a block Toeplitz matrix when the received signal consists of multiple branches, which may come from multiple antennas or oversampling of the received signal.
As can be seen from the above examples, in channel estimation processes, these matrices are typically not known a priori, and since they need to be inverted in real time, efficient techniques for inverting nearly Toeplitz matrices are highly desirable. While efficient algorithms exist for inverting Toeplitz and block Toeplitz matrices, relatively little is known about inverting nearly Toeplitz matrices. Typically, nearly Toeplitz matrices have been inverted using techniques for solving linear equations such as the Gaussian elimination, Cholesky decomposition, and the Gauss-Seidel algorithm. However, these techniques do not exploit the nearly Toeplitz structure, and thus tend to be too complex to implement efficiently. In Friedlander, B., et al., “New Inversion Formulas for Matrices Classified in Terms of Their Distance From Toeplitz Matrices,” Linear Algebra and its Applications, Vol. 27, pp. 31-60, 1979, an algorithm was proposed for inverting a class of nearly Toeplitz matrices based on the notion of displacement rank. This algorithm is quite complex to implement and provides computational benefits only for those matrices with low displacement ranks. In co-owned PCT application WO 02/15505, an algorithm is proposed for inverting a specific form of nearly Toeplitz matrix of the form, (CHC+σ2I), where C is an Lf×Lf truncated convolutional matrix of the channel response. However, the algorithm proposed in WO 02/15505 is also complex and only works for matrices in this specific form, but not for other nearly Toeplitz matrices in general.